package DoublyLinkedListSentinel;

import java.util.Iterator;

public class DoublyLinkedListSentinel implements Iterable<Integer>{
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
          Node p = head.next;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    static class Node{
        Node prev;   //上一个节点指针
        int value;   //值
        Node next;   //下一个节点指针

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }
    private Node head; // 头哨兵
    private Node tail; // 尾哨兵
    public DoublyLinkedListSentinel(){
         head = new Node(null,999,null);
         tail = new Node(null,888,null);
         head.next = tail;
         tail.prev = head;
    }
    public Node findNode(int index){
        int i = -1;
        for(Node p = head;p != tail; p = p.next,i++){
            if(i == index){
                return p ;
            }
        }
        return null;
    }
    public void addFirst(int value){
         insert(value,0);
    }
    public void removeFirst(){
          remove(0);
    }
    public void addLast(int value){
        Node last = tail.prev;
        Node add = new Node(last,value,tail);
        last.next = add;
        tail.prev = add;
    }
    public void removeLast(){
        Node removed = tail.prev;
        if(removed == head){
            illegalIndex(0);
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;
    }
    public void remove(int index){
        Node prev = findNode(index-1);
        if(prev == null ){
            illegalIndex(index);
        }
        Node removed = prev.next;
        if(removed == tail){
            illegalIndex(index);
        }
        Node next = removed.next;
        prev.next = next;
        next.prev = prev;
    }
    public void insert(int value,int index){
        Node prev = findNode(index-1);
        if( prev == null) {
            illegalIndex(index);
        }
        Node next = prev.next;
        Node insert = new Node(prev,value,next);
        prev.next = insert;
        next.prev = insert;
    }

    private static void illegalIndex(int index) {
         throw new IllegalArgumentException(
                String.format("index[%d] 不合法%n", index)
        );
    }
}
